package problem23_Merge_kSorted_Lists;

/**
 * @see <a href="http://www.jiuzhang.com/solutions/merge-k-sorted-lists/" />
 * @author Ivan
 *
 */
public class MySolution {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}
	
	public ListNode mergeKLists(ListNode[] lists) {
		if(lists.length==0) return null;
		if(lists.length==1)return lists[0];
		return mergeKLists(lists,0,lists.length-1);
	}
	
	private ListNode mergeKLists(ListNode[] lists,int start,int end){
		if(start==end) return lists[start];
		int mid=(start+end)/2;
		ListNode left=mergeKLists(lists,start,mid);
		ListNode right=mergeKLists(lists,mid+1,end);
		return mergeTwoLists(left,right);
	}
	
	private ListNode mergeTwoLists(ListNode node1,ListNode node2){
		ListNode dummy=new ListNode(-1);
		ListNode head1=node1,head2=node2,tail=dummy;
		while(head1!=null&&head2!=null){
			if(head1.val<head2.val){
				tail.next=head1;
				head1=head1.next;
			}else{
				tail.next=head2;
				head2=head2.next;
			}
			tail=tail.next;
		}
		tail.next=head1==null?head2:head1;
		return dummy.next;
	}
	
	public static void main(String[] args){
		ListNode[] lists=new ListNode[4];
		ListNode node1=null;
		ListNode node2=new MySolution().new ListNode(3);
		node2.next=new MySolution().new ListNode(4);
		ListNode node3=null;
		ListNode node4=new MySolution().new ListNode(5);
		node2.next=new MySolution().new ListNode(6);
		lists[0]=node1;
		lists[1]=node2;
		lists[2]=node3;
		lists[3]=node4;
		new MySolution().mergeKLists(lists);
	}
}
